package twobranchsearch.Treebfsiterator;

import java.util.LinkedList;

import twobranchTree.preorderTraversal.TreeNode;

/**
 * @Date 2020/03/10
 * @author 王光浩
 * @Thinking 首先将二叉搜索树按照中序遍历的方式，将遍历的结果保存在数组中，然后直接使用即可。
 * @Analysis 时间复杂度O（n），空间复杂度O（height+n）
 */
public class MyMethodOn {
	LinkedList<Integer> res;  //保存二叉搜索树的中序遍历结果
	/** 初始化 */
    public MyMethodOn(TreeNode root) {
    	res=new LinkedList<Integer>();
    	recursively(root);
    }
    
    /** @return the next smallest number */
    public int next() {
    	return res.poll();
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
    	return !res.isEmpty();
    }
    /**
     * 进行中序遍历
     * @param root
     */
    private void recursively(TreeNode root) {
    	if(root==null)return;
    	recursively(root.left);
    	res.add(root.val);
    	recursively(root.right);
    }
}
